//https://leetcode.cn/problems/0ynMMM/
//思想：参考单调栈实现即可；
//类似题目1：sub累加和*sub中的最小值；leetcode有原题，但是不是会员；
//类似题目2：子数组的两端，一个是该子数组的最小值，一个是该子数组的次最小值；

#include <vector>
#include <stack>
#include <list>
#include <map>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        std::vector<std::pair<int,int>> res(heights.size(),{-1,-1});
        std::stack<std::list<int>> stack;
        for(size_t i=0;i<heights.size();++i){
            while(!stack.empty()&& heights[stack.top().back()] > heights[i]) {
                std::list<int> popIs=stack.top();
                stack.pop();
                int leftlessIndex = stack.empty()? -1:stack.top().back();
                for(int popi:popIs){
                    res[popi].first = leftlessIndex;
                    res[popi].second = i;
                }
            }
            if(!stack.empty() && heights[stack.top().back()] == heights[i]) {
                stack.top().push_back(i);
            }else{
                std::list<int> list = {(int)i};
                stack.push(list);
            }
        }

        while(!stack.empty()){
            list<int> popIs=stack.top();
            stack.pop();
            int leftlessIndex = stack.empty()? -1:stack.top().back();
            for(int popi:popIs) {
                res[popi].first = leftlessIndex;
                res[popi].second = -1;
            }
        }
        int maxArea = 0;
        for(int i=0;i<heights.size();++i){
            auto cur_height=heights[i];
            int leftlessIndex= res[i].first ==-1? 0:res[i].first+1;
            int rightlessIndex=res[i].second == -1? heights.size()-1:res[i].second-1;
            maxArea=std::max((rightlessIndex-leftlessIndex+1)*cur_height,maxArea);
        }
        return maxArea;
    }
};